package com.example.arithmeticleetcode.leetcode.feb2021;

import org.apache.logging.log4j.util.Chars;

import java.util.*;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2021-02-19 15:59
 **/
public class Demo01 {

    public TreeNode increasingBST(TreeNode root) {
        return null;
    }

    /**
     * 1004. 最大连续1的个数 III
     *
     * @param A
     * @param K
     * @return
     */
    public int longestOnes(int[] A, int K) {
        return 0;
    }


    /**
     * 965. 单值二叉树 BFS
     *
     * @param root
     * @return
     */
    public boolean isUnivalTree(TreeNode root) {
        int first = root.val;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.val != first) return false;
            if (node != null) {
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
        }
        return true;
    }

    /**
     * 965. 单值二叉树 DFS
     *
     * @param root
     * @return
     */
    private Set<Integer> set;

    public boolean isUnivalTreeDFS(TreeNode root) {
        set = new HashSet<>();
        dfs(root);
        return set.size() == 1;
    }

    private void dfs(TreeNode node) {
        if (node != null) {
            set.add(node.val);
            dfs(node.left);
            dfs(node.right);
        }
    }

    public static void main(String[] args) {
        String str = "Bob hit a ,,ball,,,, the hit BALL flew far after it was hit.";
        String[] banned = {"hit"};
        System.out.println(mostCommonWord(str, banned));
        String str1 = "a.";
        String[] banned1 = {};
        System.out.println(mostCommonWord(str1, banned1));
        String str2 = "Bob";
        String[] banned2 = {};
        System.out.println(mostCommonWord(str2, banned2));
        String str3 = "Bob. hIt, baLl";
        String[] banned3 = {"bob", "hit"};
        System.out.println(mostCommonWord(str3, banned3));
    }


    /**
     * 819. 最常见的单词
     *
     * @param paragraph
     * @param banned
     * @return
     */
    public static String mostCommonWord(String paragraph, String[] banned) {
        String lowerStrings = paragraph.toLowerCase();
        Map<String, Integer> map = new HashMap<>();
        char[] chars = lowerStrings.toCharArray();
        int preIndex = 0;
        boolean flag = true;
        boolean lastFlag = false;
        for (int i = 0; i < chars.length; i++) {
            //是字母
            if (flag && chars[i] >= 97 && chars[i] <= 122) {
                flag = false;
                lastFlag = false;
                preIndex = i;
            } else if (chars[i] >= 97 && chars[i] <= 122) {
                lastFlag = true;
                continue;
            } else if (!flag) {
                String s = new String(chars, preIndex, i - preIndex);
                map.put(s, map.getOrDefault(s, 0) + 1);
                flag = true;
                lastFlag = false;
            }

        }
        if (lastFlag) {
            String s = new String(chars, preIndex, chars.length - preIndex);
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        //过滤禁止的字符串
        for (String s : banned) {
            map.remove(s);
        }
        //拿到最多的字符串
        String retStr = null;
        int maxCount = Integer.MIN_VALUE;
        for (Map.Entry<String, Integer> stringIntegerEntry : map.entrySet()) {
            if (maxCount < stringIntegerEntry.getValue()) {
                retStr = stringIntegerEntry.getKey();
                maxCount = stringIntegerEntry.getValue();
            }
        }
        return retStr;
    }


    /**
     * 700. 二叉搜索树中的搜索
     *
     * @param root
     * @param val
     * @return
     */
    private TreeNode node = null;
    public TreeNode searchBST(TreeNode root, int val) {
        if (root == null) return null;
        dfs(root, val);
        return node;
    }

    private void dfs(TreeNode root, int val) {
        if (root == null) return;
        if (root.val == val) {
            node = root;
            return;
        }
        if (root.left != null) {
            dfs(root.left, val);
        }
        if (root.right != null) {
            dfs(root.right, val);
        }
    }

    /**
     * 700. 二叉搜索树中的搜索 dfs
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST2(TreeNode root, int val) {
        if (root == null || root.val == val) return root;
        return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
    }

    /**
     * 700. 二叉搜索树中的搜索 dfs
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST3(TreeNode root, int val) {
        if (root == null || root.val == val) return root;
        return val < root.val ? searchBST(root.left, val) : searchBST(root.right, val);
    }

    /**
     * 700. 二叉搜索树中的搜索 迭代
     *
     * @param root
     * @param val
     * @return
     */
    public TreeNode searchBST4(TreeNode root, int val) {
        while (root != null || root.val != val)  root = val < root.val ? root.left : root.right;
        return root;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}


class Foo {

    public Foo() {

    }

    public void first(Runnable printFirst) throws InterruptedException {

        // printFirst.run() outputs "first". Do not change or remove this line.
        printFirst.run();
    }

    public void second(Runnable printSecond) throws InterruptedException {

        // printSecond.run() outputs "second". Do not change or remove this line.
        printSecond.run();
    }

    public void third(Runnable printThird) throws InterruptedException {

        // printThird.run() outputs "third". Do not change or remove this line.
        printThird.run();
    }
}

class MyHashSet {

    private List<Integer> list;

    /**
     * Initialize your data structure here.
     */
    public MyHashSet() {
        list = new ArrayList<>();
    }

    public void add(int key) {
        if (list.contains(key)) return;
        list.add(key);
    }

    public void remove(int key) {
        if (list.contains(key)) {
            Iterator<Integer> iterator = list.iterator();
            while (iterator.hasNext()) {
                if (iterator.next() == key) {
                    iterator.remove();
                    return;
                }
            }
        }
    }

    /**
     * Returns true if this set contains the specified element
     */
    public boolean contains(int key) {
        return list.contains(key);
    }
}

class MyHashSet2 {

    private boolean[] arr;

    /**
     * Initialize your data structure here.
     */
    public MyHashSet2() {
        arr = new boolean[1000000];
    }

    public void add(int key) {
        arr[key] = true;
    }

    public void remove(int key) {
        arr[key] = false;
    }

    /**
     * Returns true if this set contains the specified element
     */
    public boolean contains(int key) {
        return arr[key] == true;
    }
}